索引类似于书本的目录，能够提高数据查询效率。
常见的索引模型
- 哈希表
key-value的数据存储结构。通过哈希函数将key换算成一个具体的数组位置，将value放在对应的数组位置。多余哈希冲突，则使用拉链法进行解决。
- 插入很快。因为可以直接往后追加
- 区间查询速度很慢。因为因为数据存储不是有序的。
- 哈希表适合等值查询的场景(Memcached和一些NoSQL引擎)
- 有序数组
有序数组在等值查询和范围查询的场景中的性能都非常优秀。
- 查询效率高，利用二分法进行查询。，同样也支持范围查询
- 新增记录成本太高，因为每增加一条新纪录，都要挪动后面所有的记录
所以有序数组适合静态存储引擎，如2017年某个城市的所有人口信息。
- 搜索树
- 二叉搜索树
左子节点小于父节点，父节点小于右子节点。
查询复杂度：O(log(n))
更新时间复杂度：O(log(n))
- 数据库为什么不使用二叉树而选择多叉树
（1）二叉树虽然效率高，但是每一层存储的数据量比较少。假如在特别大的数据量的情况下，使用二叉树会导致树的层数非常高。层数越多，访问磁盘的次数越多，磁盘读取往往是性能的瓶颈，所以二叉树的读取性能就回很差。
（2）为了尽量的少读磁盘，让查询过程访问尽量少的数据块，应该使用多叉树。假如一个N=1200的多叉树，树高为4，可以存储1200的三次方的数据(17亿)。也就是在这17亿的数据中，查找一条记录，最多访问磁盘三次。
InnoDB的索引模型
InnoDB的索引模型：B+树索引模型,每一个索引在InnoDB中就对应一棵B+树
B+树索引类型
- 主键索引(聚簇索引)
叶子节点存储整行数据
- 普通索引(二级索引)
叶子节点存储的是主键的值
主键索引和非主键索引的区别
- 通过主键查询的方式，就是直接搜索主键索引这棵B+树。
- 如果通过普通索引的方式，则是先通过普通索引B+树查询到主键值，再通过主键值去主键索引B+树里面所有(回表)
普通索引会多扫描一次索引，应该优先使用主键索引
索引维护
B+树维护了索引的有效性，当插入新值的时候，就要做必要的维护
- 页分裂
当插入数据所在页的数据页满了，就要重新申请一个新的数据页，让后再挪动部分数据过去。性能受影响。
- 页合并
相邻两个数据页因为删除了数据，利用率很低之后，会将数据页进行合并。
自增字段的重要性
索引的维护过程中，会出现页分裂和页合并的现象，这些是比较耗费性能的。所以现在的建表规范里面都要求使用自增字段。那自增字段能够对索引维护起到什么作用吗？
- 自增逐渐的插入数据模式都是追加操作，不会涉及挪动其他记录，不会触发叶子节点的分裂。—-性能
- 如果使用业务字段做主键，不容易保证有序插入，写数据成本高。—-性能
- 自增逐渐相比业务字段作逐渐节省存储空间。如果使用身份证之类的作为主键，那么普通索引的叶子节点(主键)就会占用比较多的存储空间(字符串20个字节)，整型(4个字节)，长整型(8个字节)。—-存储空间
主键长度约小，普通索引的叶子节点就越小，普通索引占用的空间就越小
业务字段作为主键的场景：
- 只有一个索引
- 该索引是唯一索引
